import java.util.ArrayList;
import java.util.List;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/1 19:49
 */
// 括号生成
    // 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
    // dp[j] 代表 对数为j的可能并且有效的括号组合
    //
//示例 1：
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
public class Solution22 {
    public List<String> generateParenthesis(int n) {
        // 边界处理
        if (n == 0) return new ArrayList<>();
        List<String> result = new ArrayList<>();
        // 记录路径用于回溯
        StringBuilder track = new StringBuilder();
        backtrack(n, n, track, result);
        return result;
    }

    // 回溯算法
    private void backtrack(int left, int right, StringBuilder track, List<String> result) {
        if (left < 0 || right < 0) return;
        // 左括号剩多了
        if (right < left) return;
        // 括号恰好用完
        if (left == 0 && right == 0) {
            result.add(track.toString());
            return;
        }
        track.append('(');  //选择
        backtrack(left - 1, right, track, result);
        track.deleteCharAt(track.length() - 1); // 撤销选择

        track.append(')');
        backtrack(left, right - 1, track, result);
        track.deleteCharAt(track.length() - 1);
    }
}
